package com.zofer.study.linkedlist;

/**
 * 题目：输入两个链表，找出它们的第一个公共结点。
 */
public class FindFirstCommonNode {

    /**
     * 思路：两个链表如果有公共节点,一定是Y字形。
     * 第一步：求出两个队列的长度
     * 第二步：求出两个长度的差n,长的队列先走n步
     * 第三步：比较两个链表的节点，不相等，一直比较下去直到相等
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == pHead2){
            return pHead1;
        }

        ListNode pHeadtem1 = pHead1;
        int size1 = 0;
        while(pHeadtem1 != null){
            size1++;
            pHeadtem1 = pHeadtem1.next;
        }

        ListNode pHeadtem2 = pHead2;
        int size2 = 0;
        while(pHeadtem2 != null){
            size2++;
            pHeadtem2 = pHeadtem2.next;
        }

        ListNode longNode = pHead1;
        ListNode shortNode = pHead2;
        int diff = 0;
        if(size2 > size1){
            longNode = pHead2;
            shortNode = pHead1;
            diff = size2 - size1;
        }else{
            longNode = pHead1;
            shortNode = pHead2;
            diff = size1 - size2;
        }

        for(int i = 0;i < diff;i++){
            longNode = longNode.next;
        }

        while(longNode != shortNode){
            longNode = longNode.next;
            shortNode = shortNode.next;
        }
        return longNode;

    }
}
